#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <limits>

using namespace std;

typedef int WeightType;

struct Edge
{
	Edge(int vv, WeightType ww) : v(vv), w(ww) {}
	int v;
	WeightType w;
};

// O(V*E)
vector<WeightType> BellmanFord(const vector<list<Edge> > &t, int src)
{
	vector<WeightType> res(t.size(), numeric_limits<WeightType>::max());
	res[src] = 0;

	for (int i = 1; i < t.size(); ++i)
		for (int j = 0; j < t.size(); ++j)
			if (res[j] != numeric_limits<WeightType>::max())
				for (list<Edge>::const_iterator k = t[j].begin(); k != t[j].end(); ++k)
					res[k->v] = min(res[k->v], res[j] + k->w);

	return res;
}

// O(V^2 + E)
vector<WeightType> Dijkstra(const vector<list<Edge> > &t, int src)
{
	vector<WeightType> res(t.size(), numeric_limits<WeightType>::max());
	vector<bool> f(t.size(), false);
	res[src] = 0;

	for (int i = 1; i < t.size(); ++i)
	{
		// find the vertex with the minimum distance and is not determined.
		int idx;
		WeightType minDist = numeric_limits<WeightType>::max();
		for (int j = 0; j < t.size(); ++j)
			if (!f[j] && res[j] < minDist)
			{
				minDist = res[j];
				idx = j;
			}

		if (minDist != numeric_limits<WeightType>::max())
		{
			f[idx] = true;

			// relax
			for (list<Edge>::const_iterator j = t[idx].begin(); j != t[idx].end(); ++j)
				res[j->v] = min(res[j->v], res[idx] + j->w);
		}
	}

	return res;
}

// O(K*E), K << V
vector<WeightType> Spfa(const vector<list<Edge> > &t, int src)
{
	vector<WeightType> res(t.size(), numeric_limits<WeightType>::max());
	queue<int> q;
	vector<bool> inQ(t.size(), false);
	
	res[src] = 0;
	q.push(src);
	inQ[src] = true;

	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		inQ[u] = false;

		for (list<Edge>::const_iterator i = t[u].begin(); i != t[u].end(); ++i)
		{
			WeightType dist = res[u] + i->w;
			if (dist < res[i->v])
			{
				res[i->v] = dist;
				if (!inQ[i->v])
				{
					q.push(i->v);
					inQ[i->v] = true;
				}
			}
		}
	}

	return res;
}
